{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flip Game II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming #backtracking #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划 #回溯 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canWin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转游戏 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：</p>\n",
    "\n",
    "<p>给你一个字符串 <code>currentState</code> ，其中只含 <code>'+'</code> 和 <code>'-'</code> 。你和朋友轮流将&nbsp;<strong>连续 </strong>的两个&nbsp;<code>\"++\"</code>&nbsp;反转成&nbsp;<code>\"--\"</code> 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。默认每个人都会采取最优策略。</p>\n",
    "\n",
    "<p>请你写出一个函数来判定起始玩家 <strong>是否存在必胜的方案</strong> ：如果存在，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>currentState = \"++++\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>起始玩家可将中间的 <code>\"++\"</code> 翻转变为 <code>\"+--+\" 从而得胜。</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>currentState = \"+\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= currentState.length &lt;= 60</code></li>\n",
    "\t<li><code>currentState[i]</code> 不是 <code>'+'</code> 就是 <code>'-'</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>请推导你算法的时间复杂度。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flip-game-ii](https://leetcode.cn/problems/flip-game-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flip-game-ii](https://leetcode.cn/problems/flip-game-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"++++\"', '\"+\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        self.memo = {}\n",
    "\n",
    "        def dfs(s):\n",
    "            if s in self.memo:\n",
    "                return self.memo[s]\n",
    "\n",
    "            for i in range(len(s) - 1):\n",
    "                if s[i:i+2] == '++' and not dfs(s[:i] + '--' + s[i+2:]):\n",
    "                    self.memo[s] = True\n",
    "                    return True\n",
    "            self.memo[s] = False\n",
    "            return False\n",
    "        return dfs(currentState)\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        ans = False\n",
    "        n = len(currentState)\n",
    "\n",
    "        def dfs(s):\n",
    "            if \"++\" not in s:\n",
    "                return False\n",
    "            \n",
    "            for i in range(n - 1):\n",
    "                if s[i: i + 2] == \"++\":\n",
    "                \n",
    "                    if not dfs(s[:i] + \"--\" + s[i+2:]):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        ans = dfs(currentState)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nim = [0] * 61\n",
    "        for i in range(2, 61):\n",
    "            s = set()\n",
    "            j = 0\n",
    "            while j <= i - j - 2:\n",
    "                s.add(self.nim[j] ^ self.nim[i-j-2])\n",
    "                j += 1\n",
    "            while self.nim[i] in s:\n",
    "                self.nim[i] += 1\n",
    "        print(self.nim)\n",
    "        \n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        return reduce(lambda x, y: x ^ y, (self.nim[len(s)] for s in currentState.split('-'))) > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = list(currentState)\n",
    "        n = len(s)\n",
    "        for i in range(n - 1):\n",
    "            if s[i] == '+' and  s[i+1] == '+':\n",
    "                s[i] = '-'\n",
    "                s[i+1] = '-'\n",
    "                if self.canWin( ''.join(s) ) == False:\n",
    "                    return True\n",
    "                s[i] = '+'              #回溯，有借有还\n",
    "                s[i+1] = '+'            #回溯，有借有还\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "        n = len(currentState)\n",
    "        for i in range(1, n):\n",
    "            if currentState[i - 1:i + 1] == '++' and not self.canWin(currentState[:i - 1] + '--' + currentState[i + 1:]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "            for i in range(len(currentState) - 1):\n",
    "                if currentState[i:i+2] == '++':\n",
    "                    if not self.canWin(currentState[:i] + '--' + currentState[i+2:]):\n",
    "                        return True \n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = list(currentState)\n",
    "        n = len(s)\n",
    "        for i in range(n - 1):\n",
    "            if s[i] == '+' and  s[i+1] == '+':\n",
    "                s[i] = '-'\n",
    "                s[i+1] = '-'\n",
    "                if self.canWin( ''.join(s) ) == False:\n",
    "                    return True\n",
    "                s[i] = '+'              #回溯，有借有还\n",
    "                s[i+1] = '+'            #回溯，有借有还\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        def dfs(state):\n",
    "            for i in range(len(currentState) - 1):\n",
    "                if (state >> i) & 1 or (state >> (i + 1)) & 1:\n",
    "                    continue\n",
    "                if not dfs(state | 1 << i | state | 1 << (i + 1)):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(currentState)):\n",
    "            if currentState[i] == '-':\n",
    "                res += 1 << i\n",
    "        return dfs(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = list(currentState)\n",
    "        n = len(s)\n",
    "        for i in range(n - 1):\n",
    "            if s[i] == '+' and  s[i+1] == '+':\n",
    "                s[i] = '-'\n",
    "                s[i+1] = '-'\n",
    "                if self.canWin( ''.join(s) ) == False:\n",
    "                    return True\n",
    "                s[i] = '+'              #回溯，有借有还\n",
    "                s[i+1] = '+'            #回溯，有借有还\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s=list(currentState)\n",
    "        n=len(s)\n",
    "        for i in range(n-1):\n",
    "            if s[i]=='+' and s[i+1]=='+':\n",
    "                s[i]='-'\n",
    "                s[i+1]='-'\n",
    "                if not self.canWin(''.join(s)): # 翻到对手面后对手无法行动\n",
    "                    return True\n",
    "                else: # 如果对手能行动，则当前反转无效，进行回溯\n",
    "                    s[i]='+'\n",
    "                    s[i+1]='+'\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        a=currentState\n",
    "        currentState=[]\n",
    "        for char in a:\n",
    "            currentState.append(char)\n",
    "        \n",
    "        def dfs(judge,currentState):\n",
    "            currentState=list(currentState)\n",
    "            if judge==0:\n",
    "                ret=False\n",
    "                q=0\n",
    "                for i in range(len(currentState)-1):\n",
    "                    if currentState[i:i+2]==['+','+']:\n",
    "                        currentState[i]='-'\n",
    "                        currentState[i+1]='-'\n",
    "                        ret=ret or dfs(judge^1,tuple(currentState))\n",
    "                        currentState[i]='+'\n",
    "                        currentState[i+1]='+'\n",
    "                        q=1\n",
    "                if q==0:\n",
    "                    if judge==0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        return True\n",
    "                return ret\n",
    "\n",
    "            elif judge==1:\n",
    "                ret=True\n",
    "                q=0\n",
    "                for i in range(len(currentState)-1):\n",
    "                    if currentState[i:i+2]==['+','+']:\n",
    "                        currentState[i]='-'\n",
    "                        currentState[i+1]='-'\n",
    "                        ret=ret and dfs(judge^1,tuple(currentState))\n",
    "                        currentState[i]='+'\n",
    "                        currentState[i+1]='+'\n",
    "                        q=1\n",
    "                if q==0:\n",
    "                    if judge==0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        return True\n",
    "                return ret\n",
    "        return dfs(0,tuple(currentState))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "        def method(line,num):\n",
    "            print(line,num)\n",
    "            if \"++\" not in line:\n",
    "                return False\n",
    "            else:\n",
    "                for idt in range(len(line)-1):\n",
    "                    if line[idt]==\"+\" and line[idt+1]==\"+\":\n",
    "                        result=method(line[:idt]+\"--\"+line[idt+2:],num+1)\n",
    "                        if result==False:\n",
    "                            return True\n",
    "            return False\n",
    "        result=method(currentState,0)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = currentState\n",
    "        if '++' not in s:\n",
    "            return False\n",
    "        for idx in range(len(s)-1):\n",
    "            if s[idx:idx+2]=='++':\n",
    "                if not self.canWin(s[0:idx]+'--'+s[idx+2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s=list(currentState)\n",
    "        n=len(s)\n",
    "        for i in range(n-1):\n",
    "            if s[i]=='+' and s[i+1]=='+':\n",
    "                s[i]='-'\n",
    "                s[i+1]='-'\n",
    "                if not self.canWin(''.join(s)): # 翻到对手面后对手无法行动\n",
    "                    return True\n",
    "                else: # 如果对手能行动，则当前反转无效，进行回溯\n",
    "                    s[i]='+'\n",
    "                    s[i+1]='+'\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def generatePossibleNextMoves(self, currentState: str) -> List[str]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "        n = len(currentState)\n",
    "\n",
    "        for i in range(n):\n",
    "            if currentState[i] == \"+\" and i+1<n and currentState[i+1] == \"+\":\n",
    "                newState = currentState[:i]+\"--\"+currentState[i+2:]\n",
    "                res.append(newState)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "\n",
    "        states = dict()\n",
    "\n",
    "\n",
    "        def play(player,currentState):\n",
    "            nextMove = self.generatePossibleNextMoves(currentState)\n",
    "\n",
    "            if nextMove == []:\n",
    "                \n",
    "                return player == 1\n",
    "\n",
    "            \n",
    "            for move in nextMove:\n",
    "                nextPlayer = (player+1)%2\n",
    "\n",
    "                if nextPlayer == 0:\n",
    "                    if not play(nextPlayer, move):\n",
    "                        return False\n",
    "                if nextPlayer == 1:\n",
    "                    if play(nextPlayer, move):\n",
    "                        return True\n",
    "               \n",
    "                    \n",
    "\n",
    "                   \n",
    "            return not nextPlayer\n",
    "        \n",
    "\n",
    "        res = play(0,currentState)\n",
    "\n",
    "        return res\n",
    "                        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    # @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        nums = [int(x=='+') for x in currentState]\n",
    "        n=len(nums)\n",
    "        def dfs(nums):\n",
    "            for i in range(n-1):\n",
    "                if nums[i]==1 and nums[i+1]==1:\n",
    "                    nums[i]=0\n",
    "                    nums[i+1]=0\n",
    "                    if dfs(nums)==False:\n",
    "                        nums[i]=1\n",
    "                        nums[i+1]=1\n",
    "                        return True\n",
    "                    nums[i]=1\n",
    "                    nums[i+1]=1\n",
    "            return False\n",
    "\n",
    "        return dfs(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache()\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        for i in range(len(currentState)-1):\n",
    "            if currentState[i]==currentState[i+1]==\"+\":\n",
    "                newstate=currentState[:i]+\"--\"+currentState[i+2:]\n",
    "                if  not self.canWin(newstate):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nim = [0] * 61\n",
    "        for i in range(2, 61):\n",
    "            s = set()\n",
    "            j = 0\n",
    "            while j <= i - j - 2:\n",
    "                s.add(self.nim[j] ^ self.nim[i-j-2])\n",
    "                j += 1\n",
    "            while self.nim[i] in s:\n",
    "                self.nim[i] += 1\n",
    "        print(self.nim)\n",
    "        \n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        nim = 0\n",
    "        for s in currentState.split('-'):\n",
    "            nim ^= self.nim[len(s)]\n",
    "        return nim > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        state_list = list(currentState)\n",
    "        for idx in range(1, len(currentState)):\n",
    "            if state_list[idx] == '+' and state_list[idx - 1] == '+':\n",
    "                state_list[idx] = '-'\n",
    "                state_list[idx - 1] = '-'\n",
    "                ret = self.canWin(''.join(state_list))\n",
    "                if not ret:\n",
    "                    return True\n",
    "                state_list[idx] = '+'\n",
    "                state_list[idx - 1] = '+'\n",
    "        return  False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        def dfs(s):\n",
    "            l=list(s) \n",
    "            lens=len(s) \n",
    "            if lens<=1:\n",
    "                return False \n",
    "            for i in range(1,lens):\n",
    "                if l[i-1]==l[i]==\"+\":\n",
    "                    l[i-1]=l[i]='-'\n",
    "                    tp=dfs(\"\".join(l))\n",
    "                    l[i-1]=l[i]=\"+\"\n",
    "                    if not tp:\n",
    "                        return True \n",
    "            return False \n",
    "        if len(currentState)<2:\n",
    "            return False\n",
    "        return dfs(currentState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        stat = 0\n",
    "        n = len(currentState)\n",
    "        vis = [0] * n \n",
    "        for i in range(n):\n",
    "            if currentState[i] == '+':\n",
    "                vis[i] = 1\n",
    "        \n",
    "        \n",
    "        def dfs():\n",
    "            flag = 0\n",
    "            for i in range(n-1):\n",
    "                if vis[i] == 1 and vis[i+1] == 1:\n",
    "                    flag = 1\n",
    "                    break \n",
    "            if flag== 0:\n",
    "                return False \n",
    "            for i in range(n-1):\n",
    "                if vis[i] == 1 and vis[i+1] == 1:\n",
    "                    vis[i] = vis[i+1] = 0\n",
    "                    if not dfs():\n",
    "                        vis[i] = vis[i+1] = 1\n",
    "                        return True \n",
    "                    vis[i] = vis[i+1] = 1 \n",
    "            return False \n",
    "        \n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        stat = 0\n",
    "        n = len(currentState)\n",
    "        for i in range(n):\n",
    "            if currentState[i] == '+':\n",
    "                stat |= 1 << i \n",
    "        \n",
    "        \n",
    "        def dfs(stat):\n",
    "            flag = 0\n",
    "            for i in range(n-1):\n",
    "                if (stat >> i) & 3 == 3:\n",
    "                    flag = 1\n",
    "                    break \n",
    "            if flag== 0:\n",
    "                return False \n",
    "            for i in range(n-1):\n",
    "                if (stat >> i) & 3 == 3:\n",
    "                    if not dfs(stat & ~(3 << i)):\n",
    "                        return True \n",
    "            return False \n",
    "        \n",
    "        return dfs(stat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nim = [0] * 61\n",
    "        for i in range(2, 61):\n",
    "            s = set()\n",
    "            j = 0\n",
    "            while j <= i - j - 2:\n",
    "                s.add(self.nim[j] ^ self.nim[i-j-2])\n",
    "                j += 1\n",
    "            while self.nim[i] in s:\n",
    "                self.nim[i] += 1\n",
    "        print(self.nim)\n",
    "        \n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        return reduce(operator.xor, (self.nim[len(s)] for s in currentState.split('-'))) > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = list(currentState)\n",
    "        n = len(s)\n",
    "        for i in range(n-1):\n",
    "            if s[i] == '+' and s[i+1] == '+':\n",
    "                s[i] = '-'\n",
    "                s[i+1] = '-'\n",
    "                if self.canWin(\"\".join(s)) == False:\n",
    "                    return True\n",
    "                s[i]='+'\n",
    "                s[i+1] = '+'\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        currentState = list(currentState)\n",
    "        \n",
    "        for idx in range(len(currentState) - 1):\n",
    "            if currentState[idx] == '+' and currentState[idx + 1] == '+':\n",
    "                temp_state = currentState[:]\n",
    "                temp_state[idx], temp_state[idx + 1] = '-', '-'\n",
    "                if not self.canWin(''.join(temp_state)):\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        n = len(currentState)\n",
    "        for i in range(n-1):\n",
    "            if currentState[i] == currentState[i+1] == '+':\n",
    "                nxt_rst = self.canWin(currentState[:i]+'--'+currentState[i+2:])\n",
    "                if not nxt_rst:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canWin(self, currentState: str) -> bool:\n",
    "#         str_list = list(currentState)\n",
    "#         def dfs(cur_str_list):\n",
    "#             for i in range(len(cur_str_list) - 1):\n",
    "#                 if cur_str_list[i] == '+' and cur_str_list[i + 1] == '+':\n",
    "#                     cur_str_list[i] = '-'\n",
    "#                     cur_str_list[i + 1] = '-'\n",
    "#                     if not dfs(cur_str_list): return True\n",
    "#                     cur_str_list[i] = '+'\n",
    "#                     cur_str_list[i + 1] = '+'\n",
    "\n",
    "#             return False\n",
    "\n",
    "#         return dfs(str_list)\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = list(currentState)\n",
    "        n = len(s)\n",
    "        for i in range(n - 1):\n",
    "            if s[i] == '+' and  s[i+1] == '+':\n",
    "                s[i] = '-'\n",
    "                s[i+1] = '-'\n",
    "                if self.canWin( ''.join(s) ) == False:\n",
    "                    return True\n",
    "                s[i] = '+'              #回溯，有借有还\n",
    "                s[i+1] = '+'            #回溯，有借有还\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache()\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ### 只有两个连续的++才能变成--，可以从任何一个位置开始flip，如果变成+--+， +和+都不连续了，因此游戏就结束了，每次其实是对于初始状态有一个判断。\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        def dfs(st):\n",
    "            ### 如果++直接不存在，那么++本身就是不存在\n",
    "            if \"++\" not in st:\n",
    "                return False\n",
    "            n = len(st)\n",
    "            ## 这里为什么是n-1\n",
    "            for i in range(n-1):\n",
    "                if st[i] == st[i+1] == \"+\":\n",
    "                    ## 如果此时先手可以做出第一步反应，那么再替换它之后如果是false,就代表成功。 \n",
    "                    if not dfs(st[:i] + \"--\" + st[i+2:]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(currentState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ### 只有两个连续的++才能变成--，可以从任何一个位置开始flip，如果变成+--+， +和+都不连续了，因此游戏就结束了，每次其实是对于初始状态有一个判断。\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        def dfs(st):\n",
    "            if \"++\" not in st:\n",
    "                return False\n",
    "            n = len(st)\n",
    "            for i in range(n-1):\n",
    "                if st[i] == st[i+1] == \"+\":\n",
    "                    if not dfs(st[:i] + \"--\" + st[i+2:]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(currentState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        def dfs(state):\n",
    "            for i in range(len(currentState) - 1):\n",
    "                if (state >> i) & 1 or (state >> (i + 1)) & 1:\n",
    "                    continue\n",
    "                if not dfs(state | 1 << i | 1 << i + 1):\n",
    "                    return True\n",
    "            return False\n",
    "        res = 0\n",
    "        for i in range(len(currentState)):\n",
    "            if currentState[i] == '-':\n",
    "                res += 1 << i\n",
    "        return dfs(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        data = list(currentState)\n",
    "        n = len(data)\n",
    "        def first(data):\n",
    "            # 先手能不能赢\n",
    "            for i in range(n-1):\n",
    "                if data[i] == '+' and data[i+1] == '+':\n",
    "                    data[i] = '-'\n",
    "                    data[i+1] = '-'\n",
    "                    if not first(data):\n",
    "                        data[i] = data[i+1] = '+'\n",
    "                        return True\n",
    "                    data[i] = data[i+1] = '+'\n",
    "            return False\n",
    "        \n",
    "        \n",
    "        return first(data)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        s = list(currentState)\n",
    "        n = len(s)\n",
    "        for i in range(n-1):\n",
    "            if s[i] == s[i+1] == '+':\n",
    "                s[i] = s[i+1] = '-'\n",
    "                if self.canWin(''.join(s)) == False:\n",
    "                    return True\n",
    "                s[i] = s[i+1] = '+'\n",
    "        return False\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        # s = list(currentState)\n",
    "\n",
    "        def backtrace(s: List[str]):\n",
    "            for i in range(len(s)-1):\n",
    "                if s[i]==\"+\" and s[i+1]==\"+\":\n",
    "                    s[i],s[i+1] = \"-\",\"-\"\n",
    "                    if not backtrace(s[:]):\n",
    "                        return True\n",
    "                    s[i],s[i+1] = '+', '+'\n",
    "            return False\n",
    "        \n",
    "        return backtrace(list(currentState))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "    \n",
    "        def dfs(curState):\n",
    "            for i in range(len(curState)-1):\n",
    "                if curState[i]=='+' and curState[i+1]=='+':\n",
    "                    newState=curState[:i]+'--'+curState[i+2:]\n",
    "                    if dfs(newState) is False:\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(currentState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "        def f(s, cache):\n",
    "            if s in cache:\n",
    "                return cache[s]\n",
    "            for i in range(len(s)):\n",
    "                if i + 1 < len(s) and s[i:i + 2] == '++':\n",
    "                    if not f(s[:i] + '--' + s[i+2:], cache):\n",
    "                        cache[s] = True\n",
    "                        return True\n",
    "            else:\n",
    "                cache[s] = False\n",
    "                return False\n",
    "\n",
    "        return f(currentState, {})\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "        n = len(currentState)\n",
    "        vis = [0] * n \n",
    "\n",
    "        def dfs():\n",
    "            \n",
    "            flag = 0\n",
    "            for i in range(n-1):\n",
    "                if vis[i] == 0 or vis[i+1] == 0:\n",
    "                    flag = 1\n",
    "            if flag == 0:\n",
    "                return False  \n",
    "            for i in range(n-1):\n",
    "                if vis[i] == 0 and vis[i+1] == 0:\n",
    "                    vis[i] = vis[i+1] = 1 \n",
    "                    if not dfs():\n",
    "                        vis[i] = vis[i+1] = 0\n",
    "                        return True\n",
    "                    vis[i] = vis[i+1] = 0 \n",
    "            return False \n",
    "\n",
    "        if n == 1:\n",
    "            return False \n",
    "        for i in range(n):\n",
    "            if currentState[i] == '-':\n",
    "                vis[i] = 1 \n",
    "        return dfs()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            for i in range(len(currentState) - 1):\n",
    "                if (state >> i) & 1 or (state >> (i + 1)) & 1:\n",
    "                    continue\n",
    "                if not dfs(state | 1 << i | state | 1 << (i + 1)):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(currentState)):\n",
    "            if currentState[i] == '-':\n",
    "                res += 1 << i\n",
    "        return dfs(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(used):\n",
    "            for i in range(n - 1):\n",
    "                if ~used >> i & 1 and ~used >> (i + 1) & 1:\n",
    "                    if not dfs(used | (1 << i) | (1 << (i + 1))):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        n = len(currentState)\n",
    "        used = 0\n",
    "        for i in range(n):\n",
    "            if currentState[i] == '-': used |= 1 << i\n",
    "        return dfs(used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def generatePossibleNextMoves(self, currentState: str) -> List[str]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "        n = len(currentState)\n",
    "\n",
    "        for i in range(n):\n",
    "            if currentState[i] == \"+\" and i+1<n and currentState[i+1] == \"+\":\n",
    "                newState = currentState[:i]+\"--\"+currentState[i+2:]\n",
    "                res.append(newState)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "\n",
    "        states = dict()\n",
    "\n",
    "\n",
    "        def play(player,currentState):\n",
    "            nextMove = self.generatePossibleNextMoves(currentState)\n",
    "\n",
    "            if nextMove == []:\n",
    "                \n",
    "                return player == 1\n",
    "\n",
    "\n",
    "            if(player,currentState) in states:\n",
    "                return False\n",
    "            \n",
    "            for move in nextMove:\n",
    "                nextPlayer = (player+1)%2\n",
    "\n",
    "                if nextPlayer == 0:\n",
    "                    if not play(nextPlayer, move):\n",
    "                        states[(player,currentState)] = False\n",
    "                        return False\n",
    "\n",
    "                # if player 0 makes this move, and win, then win\n",
    "                if nextPlayer == 1:\n",
    "                    if play(nextPlayer, move):\n",
    "                        return True\n",
    "               \n",
    "            res = not nextPlayer\n",
    "            if not res:\n",
    "                states[(player,currentState)] = False\n",
    "            return res\n",
    "\n",
    "        \n",
    "\n",
    "        res = play(0,currentState)\n",
    "\n",
    "        return res\n",
    "                        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            for i in range(len(currentState) - 1):\n",
    "                if (state >> i) & 1 or (state >> (i + 1)) & 1:\n",
    "                    continue\n",
    "                if not dfs(state | 1 << i | 1 << i + 1):\n",
    "                    return True\n",
    "            return False\n",
    "        res = 0\n",
    "        for i in range(len(currentState)):\n",
    "            if currentState[i] == '-':\n",
    "                res += 1 << i\n",
    "        return dfs(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        n = len(currentState)\n",
    "        v = 0 \n",
    "        for i in range(n):\n",
    "            if currentState[i] == '+':\n",
    "                v |= 1 << i \n",
    "        @cache \n",
    "        def dfs(v):\n",
    "            for i in range(n-1):\n",
    "                x = 3 << i \n",
    "                if v & x == x and not dfs(v ^ x):\n",
    "                    return True \n",
    "            return False \n",
    "\n",
    "        return dfs(v)  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(st):\n",
    "            if \"++\" not in st:\n",
    "                return False\n",
    "            n = len(st)\n",
    "            for i in range(n-1):\n",
    "                if st[i] == st[i+1] == \"+\":\n",
    "                    if not dfs(st[:i] + \"--\" + st[i+2:]):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(currentState)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    memo = {}\n",
    "\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        if currentState in self.memo:\n",
    "            return self.memo[currentState]\n",
    "        for i in range(len(currentState) - 1):\n",
    "            if currentState[i] == \"+\" and currentState[i + 1] == \"+\":\n",
    "                if not self.canWin(currentState[:i] + \"--\" +\n",
    "                                   currentState[i + 2:]):\n",
    "                    self.memo[currentState] = True\n",
    "                    return True\n",
    "        self.memo[currentState] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        for i in range(len(currentState)-1):\n",
    "            if currentState[i]==currentState[i+1]==\"+\":\n",
    "                newstate=currentState[:i]+\"--\"+currentState[i+2:]\n",
    "                if  not self.canWin(newstate):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        n = len(currentState)\n",
    "        cs = list(currentState)\n",
    "        for i in range(n-1):\n",
    "            if cs[i] == cs[i+1] == \"+\":\n",
    "                cs[i] = \"-\"\n",
    "                cs[i+1] = \"-\"\n",
    "                if self.canWin(\"\".join(cs)) == False :\n",
    "                    return True \n",
    "                cs[i] = \"+\"\n",
    "                cs[i+1] = \"+\"\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        L = list(currentState)\n",
    "        n = len(L)\n",
    "        for i in range(n - 1):\n",
    "            if L[i] == '+' and L[i + 1] == '+':\n",
    "                L[i] = L[i + 1] = '-'\n",
    "                if not self.canWin(''.join(L)):\n",
    "                    return True \n",
    "                L[i] = L[i + 1] = '+'\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "        L = list(currentState)\n",
    "        n = len(L)\n",
    "        for i in range(n - 1):\n",
    "            if L[i] == '+' and L[i + 1] == '+':\n",
    "                L[i] = L[i + 1] = '-'\n",
    "                if not self.canWin(''.join(L)):\n",
    "                    return True \n",
    "                L[i] = L[i + 1] = '+'\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def canWin(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        for i in range(length - 1):\n",
    "            if s[i] == \"+\" and s[i + 1] == \"+\":\n",
    "                if not self.canWin(s[:i] + \"--\" + s[i + 2:]):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "        n = len(currentState)\n",
    "        for i in range(1, n):\n",
    "            if currentState[i - 1:i + 1] == '++' and not self.canWin(currentState[:i - 1] + '--' + currentState[i + 1:]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    记忆化搜索 + 博弈论DP\n",
    "    要理解每个人都采用最优策略的意思：如果存在多种可能的操作，其中有的操作可能会导致下一轮另一个操作的人赢，有些操作可能能保证自己赢，那么本次操作的人\n",
    "    一定会选择让自己赢的操作方式，换句话说只要有能让下一个人一定输的方式，当前操作人一定就会选择这种方式\n",
    "    先后手的交错隐藏在上面的最优策略里，而不用单独用一个变量记录当前是先手、下一轮是后手这种\n",
    "    '''\n",
    "    @cache\n",
    "    def canWin(self, currentState: str) -> bool:\n",
    "\n",
    "        n = len(currentState)\n",
    "        for i in range(1, n):\n",
    "            '''\n",
    "            遍历所有替换的可能，只要有一种可能能让下一轮不赢，那么就可以直接终止了（最优策略）\n",
    "            '''\n",
    "            if currentState[i - 1:i + 1] == '++' and not self.canWin(currentState[:i - 1] + '--' + currentState[i + 1:]):\n",
    "                return True\n",
    "        return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
